//
//  main.cpp
//  BSTree
//
//  Created by Shane on 17/9/22.
//  Copyright © 2017年 Shane. All rights reserved.
//

#include <iostream>
#include "BSTree.hpp"

int main(int argc, const char * argv[]) {
    BSTree<int> *tree = new BSTree<int>;
    std::cout << "建树" << endl;
    int a[] = {5,3,6,2,4};
    for (int i = 0; i < sizeof(a)/sizeof(a[1]); ++i) {
        tree->insert(a[i]);
    }
    std::cout << "节点总数：" << tree->size() << endl;
    std::cout << "叶子节点数：" << tree->leaf() << endl;
    std::cout << "树的高度: "<< tree->height() << endl;
    std::cout << "最大值: " << tree->maximum() << endl;
    std::cout << "最小值: "<< tree->minimum() << endl << endl;
    
    std::cout << "前序遍历" << endl;
    tree->preOrder();
    std::cout << "中序遍历" << endl;
    tree->inOrder();
    std::cout << "后序遍历" << endl;
    tree->postOrder();
    std::cout << endl;
    int element = a[1];
    BSTNode<int> *node = tree->search(element);
    if (!node) {
        std::cout << "节点 " << element << "不在树中！" << endl;
    }else{
        std::cout << "节点 " << element << " 查找成功！" << endl;
        node = tree->predecessor(element);
        if (!node) {
            std::cout << element << " 没有前驱" << endl;
        }else{
            std::cout << element << " 的前驱是: "<<node->data << endl;
        }
        
        node = tree->sucessor(element);
        if (!node) {
            std::cout << element << " 没有后继" << endl << endl;
        }else{
            std::cout << element << " 的后继是: "<<node->data << endl << endl;
        }
    }
    
    if (tree->remove(element)) {
        std::cout << "删除节点 " << element << " 成功" << endl;
        std::cout << "节点总数：" << tree->size() << endl;
        std::cout << "树的高度: "<< tree->height() << endl;
        std::cout << "叶子节点数：" << tree->leaf() << endl;
        std::cout << "中序遍历" << endl;
        tree->inOrder();

    }
    
    std::cout << endl <<  "销毁树的顺序" << endl;
    tree->destroy();
    std::cout << endl << "节点总数：" << tree->size() << endl;
    std::cout << "树的高度: "<< tree->height() << endl;

    
    delete tree;
    return 0;
}
